/**
 * 
 */
package sort;

/**
 * @author Thomas Xu
 *
 */
public class HeapSort {
	
	public static void sort(int[] arr, boolean asc){
		if(asc){
			for(int i = arr.length/2 ; i>=0;i--){
				maxHeapify(arr, arr.length, i);
			}
			
			int size = arr.length;
			for(int i= arr.length -1 ;i>=0;i--){
				swap(arr, 0, i);
				size--;
				maxHeapify(arr, size, 0);
			}
		}else{
			for(int i = arr.length /2;i>=0;i--){
				minHeapify(arr, arr.length, i);
			}
			
			int size = arr.length;
			for(int i=arr.length -1;i>=0;i--){
				swap(arr, i, 0);
				size --;
				minHeapify(arr, size, 0);
			}
		}
	}
	
	private static void minHeapify(int[] arr, int length, int index){
		int smallest = index;
		int left = left(index);
		int right = right(index);
		
		if(left < length && arr[smallest] > arr[left]) smallest = left;
		if(right < length && arr[smallest] > arr[right]) smallest = right;
		
		if(smallest != index){
			swap(arr, smallest, index);
			minHeapify(arr, length, smallest);
		}
	}
	
	private static void maxHeapify(int[] arr, int length, int index ){
		int largest = index;
		int left = left(index);
		int right = right(index);
		
		if(left < length && arr[largest] < arr[left]) largest = left;
		
		if(right < length && arr[largest] < arr[right]) largest = right;
		
		if(largest != index){
			swap (arr, largest, index);
			maxHeapify(arr, length, largest);
		}
		
	}
	
	private static int left(int index) { return index * 2 + 1;}
	private static int right(int index) { return index * 2 + 2;}
	private static int parent(int index) { return index%2 == 1? (index -1)/ 2 : (index - 2)/ 2;}

	private static void swap(int[] arr, int a, int b){
		int temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}
}
